#define TTIProgReq_BinarySearchTreeADTHeader_h

#ifndef TTIProgReq_BinarySearchTreeADTOperations_h
#define TTIProgReq_BinarySearchTreeADTOperations_h

#include "BinarySearchTreeADTHeader.h"



#ifndef TTIProgReq_Pathsum_h
#define TTIProgReq_Pathsum_h

/* Find a path of the tree with a given sum. */

// Essential idea: Starting from the root, follow a path and keep adding the elements on this path. If the sum exceeds 
// the prescribed sum (implicitly it is assumed that the tree contains only non-negative numbers), then stop and
// retrace to the parent of the current node and follow another path. 

void pathsum(node *root,int sumpath,int *found, int *sum)
{
    if(root)
        if(*sum<=sumpath)
        {
            *sum +=root->info;                 
            if(*sum>sumpath)   //This takes care of the scenario when sum of a path exceeds the specified sum
            {
                *sum-=root->info;
                return;
            }
            if(root->left==NULL && root->right==NULL)  
            {
                if(*sum==sumpath)  //Success: Reached a leaf node and the sum of the path equals the specified sum
                    *found=1;
            }
            else
            {
                pathsum(root->left,sumpath,found, sum);
                pathsum(root->right,sumpath,found, sum);
            }
            if(*found==1)
                cout<<root->info<<'\t';
            else
                *sum-=root->info; //This takes care of the scenario when sum of a path falls short of the specified sum
        }
    return;
}
#endif


#ifndef TTIProgReq_MirrorImage_h
#define TTIProgReq_MirrorImage_h

/* Convert the given binary search tree into its mirror image */

// Recursion similar to that involved in preorder traversal is applied. 
// Cute Observation:  Inorder traversal of a binary search tree yields a sorted list(ascending order). We can
// simply take the mirror image of the tree and inorder traversal gives the descending order.*/

node* mirror(node* root)
{
    if(root!=NULL)
	{
        node *temp;
        temp=root->left;
        root->left=root->right;
        root->right=temp;
        mirror(root->left);
        mirror(root->right);
	}
    return root;
}
#endif


#ifndef TTIProgReq_InsertElement_h
#define TTIProgReq_InsertElement_h

/* Insert new elements in a binary search tree. If the element is already present, no action is taken. */

node* insert(node *root,int num)
{
    if(root==NULL)
	{                           //Empty (sub)tree
        root=new node;
        root->left=NULL;
        root->right=NULL;
        root->info=num;
	}
    else
	{
        if(num<root->info)       //smaller numbers can be found only in the left subtree     
            root->left=insert(root->left,num);
        else if(num>root->info)  //larger numbers can be found only in the right subtree
            root->right=insert(root->right,num);
	}
    return root;
}

#endif

#ifndef TTIProgReq_DeleteElement_h
#define TTIProgReq_DeleteElement_h

#ifndef TTIProgReq_FindMinimum_h
#define TTIProgReq_FindMinimum_h
/* Auxiliary routine: Find the minimum element in the tree rooted at s */

node *findmin(node *s)
{
    if(s==NULL || s->left==NULL)
        return s;
    else
        return findmin(s->left);  //By definition, the minimum element is guaranteed to lie on the leftmost path
}

#endif

/* Delete an element from the tree. If the element is not present, no action is taken. */

node* del(node *root,int num)
{
    if(root==NULL)
        return root;
    else if(num<root->info)        // Element possibly in left subtree
        root->left=del(root->left,num);
    else if(num>root->info)        //    Element possibly in right subtree
        root->right=del(root->right,num); //
    else
	{                           // Element reached
        if(root->left && root->right)
        {                        // Both left child and right child exist
            node *temp;
            temp=findmin(root->right);
            root->info=temp->info;  //Replace the element to be deleted with the minimum element in its right subtree 
            root->right=del(root->right,root->info); //Delete the minimum element in the right subtree
            
        }
        /* Zero or one child */
        else
        {
            node *temp=root;
            if(root->left)            // Left child replaces the node to be deleted
                root=root->left;
            else
                root=root->right;       // Right child (or no child) replaces the node to be deleted
            temp->left=temp->right=NULL;
            delete temp;
        }
	}
    return root;
}


#endif


#ifndef TTIProgReq_PreorderTraversal_h
#define TTIProgReq_PreorderTraversal_h

/* Pre-order traversal */
void preorder(node *root)
{
    if(root!=NULL)
	{
        cout<<root->info<<"\t";  //First visit the given node
        preorder(root->left);   //Now visit the left child
        preorder(root->right);  //Finally visit the right child
	}
    return;
}

#endif



#ifndef TTIProgReq_InorderTraversal_h
#define TTIProgReq_InorderTraversal_h

/* In-order traversal */

void inorder(node *root)
{
    if(root)
	{
        inorder(root->left);      //First visit the left child
        cout<<root->info<<"\t";   //Now visit the given node
        inorder(root->right);     //Finally visit the right child
	}
    return;
}


#endif


#ifndef TTIProgReq_PostorderTraversal_h
#define TTIProgReq_PostorderTraversal_h

/* Post-order traversal */
void postorder(node *root)
{
    if(root)
	{
        postorder(root->left);   //First visit the left child
        postorder(root->right);  //Now visit the right child
        cout<<root->info<<'\t';  //Finally visit the given node
	}
    return;
}


#endif


#ifndef TTIProgReq_LevelOrderTraversal_h
#define TTIProgReq_LevelOrderTraversal_h

/* Level-by-level traversal */

//Essential idea: To do a level order traversal, we need to simulate a queue. Starting with the root of the tree, every 
// time a node is encountered, we need to insert its left child and right child at the rear end of the queue. Repeat
// this procedure till the queue becomes empty. 

void levelorder(node *root,lnode *front,lnode *rear)
{
    if(front)
	{
        lnode *temp;
        cout<<front->a->info<<'\t';   //visit the node at the front of the queue
        if(front->a->left)
        {                             //insert the left child if it exists
            lnode *temp;    
            temp=new lnode;
            temp->a=front->a->left;
            temp->next=NULL;
            rear->next=temp;
            rear=temp;
            temp=temp->next;
        }
        if(front->a->right)         
        {                           //insert the right child if it exists
            temp=new lnode;
            temp->a=front->a->right;
            temp->next=NULL;
            rear->next=temp;
            rear=temp;
            temp=temp->next;
        }
        temp=front;                
        front=front->next;   //move the front to the next node in the queue
        temp->next=NULL;     //free the space consumed by the node we visited
        delete temp;
        if(front==NULL)     //queue empty?
            rear=NULL;
        levelorder(root,front,rear);
	}
    return;
}


#endif


#ifndef TTIProgReq_FindNthSmallest_h
#define TTIProgReq_FindNthSmallest_h

/* Find the Nth smallest element (if it exists) in the tree. */
// Esential idea: Since the inorder traversal gives the sorted list, therefore follow a similar procedure to retrieve
// the Nth smallest element. 

void NSmallest(node *root, int N, int *found, int *i)
{
    if (root)
    {
        NSmallest(root->left, N, found, i);
        *i= *i + 1;
        if (*i==N)       
        {
            *found = 1;      //Nth smallest element found
            cout<<endl<<root->info;
        }
        NSmallest(root->right, N, found, i);            
    }    
}


#endif


#ifndef TTIProgReq_FindLeafSum_h
#define TTIProgReq_FindLeafSum_h

/* Compute the sum of leaves of the tree */

void sum_leaves(node *root, int *sum)
{
    if(root!=NULL)
    {
        if(root->left==NULL && root->right==NULL)  //reached a leaf node?
            *sum +=root->info;
        sum_leaves(root->left,sum);    //look for all leaf nodes in the left subtree
        sum_leaves(root->right,sum);   //look for all leaf nodes in the right subtree 
    }
}


#endif


#ifndef TTIProgReq_FindHeight_h
#define TTIProgReq_FindHeight_h

/* Determine the height (maximum level) of the tree. The height is defined to be -1 for an empty tree and 0 for a tree with just one element. */

int lmax(node *root,int height)
{
    if(root==NULL)    
        return -1;      //Empty tree
    else
    {
        int height1,height2;
        height1=lmax(root->left,height);   //Find the height of the left subtree
        height2=lmax(root->right,height);  //Find the height of the right subtree
        height=(height1>height2?height1:height2)+1;  //Height = height of left subtree + height of right subtree + 1
    }
    return height;
}


#endif



#ifndef TTIProgReq_FindMinLeafLevel_h
#define TTIProgReq_FindMinLeafLevel_h

/* Auxiliary routine: Find the minimum of two elements (auxiliary code) */

int min(int first,int second)
{
    return (first>second?second:first);
}

/* Determine the minimum level at which a leaf exists */

int lmin(node *root)
{
    if(root==NULL)  
        return -1;       //Empty tree
    else if(root->left==NULL && root->right==NULL)
        return 0;        //Singleton (sub)tree
    else if(root->left && root->right)  
        return min(lmin(root->left),lmin(root->right))+1; //return (1 + minimum of the left and right subtree depths) 
    else if(root->left)
        return lmin(root->left)+1;  //return (1 + minimum depth of left subtree) 
    else
        return lmin(root->right)+1; //return (1 + minimum depth of right subtree) 
}


#endif

#ifndef TTIProgReq_FindType_h
#define TTIProgReq_FindType_h

/* Determine if the tree is strictly binary or not, and complete or not. A tree is said to be strictly binary if for every node, either the node is a leaf or it has two children. A tree is said to be complete if all leaves are at the same level or depth. */

void findtype1(node *root,int *type)
{
    if(root)
    {
        if(root->left && root->right)
        {
            findtype1(root->left,type);
            findtype1(root->right,type);
        }
        else if(!(root->left) && !(root->right));
        else
        {
            *type=0;
            return;
        }
    }
}


#endif



#ifndef TTIProgReq_ConvertToCircularDoublyLinkedList_h
#define TTIProgReq_ConvertToCircularDoublyLinkedList_h

/* Obtain a sorted circular doubly linked list */

// Recursion similar to that involved in inorder traversal is applied.
void TreeToList(dnode **head,node *root)
{
    dnode *temp,*x;
    if(root!=NULL)
	{
        TreeToList(head,root->left);
        temp = (*head)->prev;
        x = new dnode;
        x->info = root->info;
        temp->next=x;
        x->next= *head;
        x->prev=temp;
        (*head)->prev=x;
        TreeToList(head,root->right);
	}
    return;
}


#endif



#ifndef TTIProgReq_Clone_h
#define TTIProgReq_Clone_h

/* Clone the tree. */

node* clone (node *root)
{
    if (root)
    {
        node* root_clone=NULL;
        root_clone = insert(root_clone, root->info);
        root_clone->left = clone(root->left);
        root_clone->right = clone(root->right);
        return root_clone;
    }
    else 
        return NULL;
}

#endif


#ifndef TTIProgReq_DeleteTree_h
#define TTIProgReq_DeleteTree_h

/* Delete the tree and free all memory. */

void delete_tree(node* root)
{
    if(root)
    {
        node* temp_left = root->left;
        node* temp_right = root->right;
        root->left = NULL;
        root->right = NULL;
        delete root;
        delete_tree(temp_left);
        delete_tree(temp_right);
    }
}

#endif

#ifndef TTIProgReq_TreeToVector_h
#define TTIProgReq_TreeToVector_h

/* Obtain an STL vector from tree using postorder traversal */
void TreeToVector(node *root, std::vector<int>* TreeVector)
{
    if(root)
	{
        TreeToVector(root->left, TreeVector);      
        TreeToVector(root->right, TreeVector);   
        (*TreeVector).push_back(root->info);   
	}
    return;
}

#endif

#ifndef TTIProgReq_TreeToListSTL_h
#define TTIProgReq_TreeToListSTL_h


/* Obtain an STL list from the tree using postorder traversal */

void TreeToListSTL(node *root, list<int> TreeList[])
{
    if(root)
	{
        TreeToListSTL(root->left, TreeList);      
        TreeToListSTL(root->right, TreeList);   
        (*TreeList).push_back(root->info);   
	}
    return;
}


#endif


#ifndef TTIProgReq_TreeSize_h
#define TTIProgReq_TreeSize_h

/* Return the number of nodes in the tree */

int TreeSize(node *root, int *size)
{
    if (root)
    {
        *size = *size + 1;
        TreeSize(root->left, size);
        TreeSize(root->right, size);
    }
    return *size;
}


#endif

#ifndef TTIProgReq_STLVectorToTree_h
#define TTIProgReq_STLVectorToTree_h


/* Obtain a tree from an STL vector */

node* VectorToTree(vector<int> VectorTree)
{
    int size = size_t(VectorTree.size());
    node *root = NULL;
    for(int i = 0; i < size; i++) 
        root=insert(root, VectorTree[i]);
    return root;
}

#endif


#ifndef TTIProgReq_ListToTree_h
#define TTIProgReq_ListToTree_h

/* Obtain a tree from an STL list */
node* ListToTree(list<int> ListTree)
{
    node *root = NULL;
    list<int>::iterator it;
    for(it = ListTree.begin(); it != ListTree.end(); ++it)
        root=insert(root, *it);
    return root;
}

#endif



#ifndef TTIProgReq_Menu_h
#define TTIProgReq_Menu_h
#include <stdio.h>
#include <string.h>

/* Input the user choice */
extern int exception_flag;

int menu()
{
    string s;
    int opt;
    cout<<endl<<"\nInstructions: Elements of tree are assumed to be non-negative integers.";
    cout<<" If you enter a float, it would be truncated to integer.\n";
    cout<<endl<<"Options:\n1.Create a tree from a vector of (positive) integers.\n2.Insert an element.";
    cout<<endl<<"3.Delete an element.\n4.Preorder traversal.";
    cout<<endl<<"5.Inorder traversal.\n6.Postorder traversal.";
    cout<<endl<<"7.Level order traversal.";
    cout<<endl<<"8.Form a sorted circular double linked list.";
    cout<<endl<<"9.Convert to the mirror image.";
    cout<<endl<<"10.Sum of leaves.";
    cout<<endl<<"11.Height of the tree.";
    cout<<endl<<"12.Minimum level at which a leaf exists.";
    cout<<endl<<"13.Determine the type of the tree.";
    cout<<endl<<"14.Find a path in the tree with a given sum.";
    cout<<endl<<"15.Find the Nth smallest element."; 
    cout<<endl<<"16.Make a clone of the tree.";
    cout<<endl<<"17.Delete the tree.";
    cout<<endl<<"18.Obtain an STL vector from the tree.";
    cout<<endl<<"19.Obtain an STL list from the tree.";
    cout<<endl<<"20.Find size of the tree. \n";
    cout<<endl<<"Enter your option: ";
    cin>>s;
    stringstream ss;
    ss<<s;
    stringstream ss_discard;  //to discard the remaining input
    try
    {
        if(ss>>opt)
        {
            getline(cin,s);
            ss_discard<<s;
        }
        else 
            throw handleInvalidMenuOption();
    }
    catch(handleInvalidMenuOption &e)
    {
        cout<<"Error code: "<< e.code()<<endl;
        getline(cin,s);
        ss_discard<<s;
        exception_flag=1;
        return e.code();
    }
    return opt;
}


#endif


#endif
